package olga.gorbatiuk.perdep.sorting.sort.impl;

import olga.gorbatiuk.perdep.sorting.sort.AbstractSort;
import olga.gorbatiuk.perdep.sorting.sort.Sort;

/**
 * @author Olga Gorbatiuk
 */
public class QuickSort extends AbstractSort implements Sort {

    /**
     * @see olga.gorbatiuk.perdep.sorting.sort.Sort#sort(int[])
     */
    @Override
    public void sort(int[] array) {
        int lowerBound = 0;
        int upperBound = array.length - 1;
        sort(array, lowerBound, upperBound);
    }

    private void sort(int[] array, int lowerBound, int upperBound) {
        int i = lowerBound;
        int j = upperBound;
        int mid = (lowerBound + upperBound) / 2;
        int x = array[mid]; // x - опорный элемент
        // посредине между
        // low и high
        do {
            while (array[i] < x) {
                ++i; // поиск элемента для переноса в старшую часть
            }
            while (array[j] > x) {
                --j; // поиск элемента для переноса в младшую часть
            }
            if (i <= j) {
                // обмен элементов местами:
                swap(i, j, array);
                // переход к следующим элементам:
                i++;
                j--;
            }
        } while (i < j);
        if (lowerBound < j) {
            sort(array, lowerBound, j);
        }
        if (i < upperBound) {
            sort(array, i, upperBound);
        }
    }
}
